package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class PathSumII {
	
	//方法一：递归法
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
    	pathSum(root, 0, targetSum, new ArrayList<>(), result);
    	return result;
    }
    
    private void pathSum(TreeNode node, int sum, int targetSum, List<Integer> path, List<List<Integer>> result) {
    	if(node == null) return;
    	
    	path.add(node.val);
    	sum += node.val;
    	
    	if(node.left == null && node.right == null && sum == targetSum)
    		result.add(new ArrayList<>(path));
    	
    	pathSum(node.left, sum, targetSum, path, result);
    	pathSum(node.right, sum, targetSum, path, result);
    	
    	path.remove(path.size() - 1);
    }
    
    //方法二：迭代法
    @SuppressWarnings("unchecked")
	public List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
    	List<List<Integer>> result = new ArrayList<>();
    	if(root == null) return result;
    	LinkedList<Object[]> stack = new LinkedList<>();
    	stack.push(new Object[] {root, 0, new ArrayList<>()});
    	
    	while(!stack.isEmpty()) {
    		Object[] arr = stack.pop();
    		TreeNode node = (TreeNode)arr[0];
    		int sum = (int)arr[1];
    		List<Integer> path = (List<Integer>)arr[2];
    		
    		path.add(node.val);
    		sum += node.val;
    		
    		if(node.left == null && node.right == null) {
    			if(sum == targetSum) 
    				result.add(path);
    		}else if(node.left != null && node.right == null) {
    			stack.push(new Object[] {node.left, sum, path});
    		}else if(node.left == null && node.right != null) {
    			stack.push(new Object[] {node.right, sum, path});
    		}else {
    			stack.push(new Object[] {node.right, sum, new ArrayList<>(path)});
    			stack.push(new Object[] {node.left, sum, path});
    		}
    	}
    	return result;
    }
    
}
